int gcd(int a, int b){
    if(b == 0)
        return a;
    else
        return gcd(b, a % b);
}

int gcd2(int a,int b){
    while(b!=0){
        int tmp=a%b;
        a=b;
        b=tmp;
    }
    return a;
}

int lcn(int a,int b){
    return a/gcd(a,b)*b;
}